package com.my.study.algorithm.linked;

/**
 * @author Carlos
 * @version 1.0
 * @Description
 * <p> 描述：
 * 输入一个长度为n链表，反转链表后，输出新链表的表头。
 * 数据范围： n <= 1000
 * 要求：空间复杂度 O(1) ，时间复杂度 O(n)。
 *
 * 如当输入链表{1,2,3}时，
 * 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
 *
 * <pre>
 *      +------+  next +-----+        +-----+
 * head |      | ----> |     | -----> |     |  tail
 *     +------+       +-----+        +-----+
 * </pre>
 *
 * <pre>
 *      +------+  prev +-----+        +-----+
 * tail |      | <---- |     | <----- |     |  head
 *     +------+       +-----+        +-----+
 * </pre>
 *
 * @date 2021/10/26 8:11
 **/
public class ReverseLink {

    public static void main(String[] args) {
        ListNode node3 = new ListNode(3, null);
        ListNode node2 = new ListNode(2, node3);
        ListNode head = new ListNode(1, node2);

        ListNode node = reverseList(head);

        System.out.println(node);
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;

        while (null != cur) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }


        return pre;
    }

}
